Mi manual de algoritmos/version_world_finals_2009/src/java/io_estandar.java

   1 import java.util.*;
   2 import java.io.*;
   3 import java.math.*;
   4
   5 class Main {
   6     public static void main(String[] args) throws IOException
   7       { BufferedReader reader = new BufferedReader(new
   8       InputStreamReader(System.in)); String line =
   9       reader.readLine(); StringTokenizer tokenizer = new
  10       StringTokenizer(line); int N =
  11       Integer.valueOf(tokenizer.nextToken()); while (N-- > 0){
  12       String a, b; a = reader.readLine(); b =
  13       reader.readLine();
  14
  15         int A = a.length(), B = b.length(); if (B > A){
  16         System.out.println("0"); }else{ BigInteger dp[][] =
  17         new BigInteger[2][A];
  18           /*
  19             dp[i][j] = cantidad de maneras diferentes
  20             en que puedo distribuir las primeras i
  21             letras de la subsecuencia (b) terminando
  22             en la letra j de la secuencia original (a)
  23           */
  24
  25           if (a.charAt(0) == b.charAt(0)){ dp[0][0] =
  26             BigInteger.ONE; }else{ dp[0][0] = BigInteger.ZERO;
  27             } for (int j=1; j<A; ++j){ dp[0][j] = dp[0][j-1];
  28             if (a.charAt(j) == b.charAt(0)){ dp[0][j] =
  29             dp[0][j].add(BigInteger.ONE); } }
  30
  31           for (int i=1; i<B; ++i){ dp[i%2][0] =
  32             BigInteger.ZERO; for (int j=1; j<A; ++j){
  33             dp[i%2][j] = dp[i%2][j-1]; if (a.charAt(j) ==
  34             b.charAt(i)){ dp[i%2][j] =
  35             dp[i%2][j].add(dp[(i+1)%2][j-1]); } } }
  36             System.out.println(dp[(B-1)%2][A-1].toString()); }
  37             } } }